package com.Algorithm.Test;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2021/10/20/19:15
 * @Description:  这个主要是解决依据目标进行排序 荷兰国旗
 * @Target:
 */
public class 解析快排步骤1 {


    public static void main(String[] args) {
        int[] arr = new int[]{1,2,1,4,6,76,4534,2};
        int R = arr.length-1;
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
        // 1,2,1,4,6,76,4534,2
        swap(arr,(0 + (int)(Math.random()*(R-0+1))),R);
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();

        partition(arr,1,arr.length-1);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    // 先思考左右指针求值问题,单层即可
    public static int[] partition(int arr[],int L,int R){
        int i = L;  // arr指针
        int less = L-1;  // 左边界
        int more = R;  // 右边界
        // 目标数
        int target = arr[R];
        // 1,2,1,4,6,76,4534,2
        while (i<R){  // 循环条件,如果i>R ---表明已经循环完了
            if(arr[i]<target){
                swap(arr,++less,i++);
            }else if(arr[i]>target){
                swap(arr,--more,i++);
            }else {
                i++;
            }
        }

        swap(arr,more,R);


        // 1.边界与末尾交换,2.如何返回边界值,

        return new int[]{less+1,more};



    }



    public static int[] swap(int arr[],int i,int j){
        int m = arr[i];
        arr[i] = arr[j];
        arr[j] = m;
        return arr;
    }

}
